843 - Crypt kicker/843.cpp

   1 #include <sstream>
   2 #include <iostream>
   3 #include <map>
   4 #include <string>
   5 #include <vector>
   6 #include <set>
   7
   8 using namespace std;
   9
  10 map<int, set<string> > dict;
  11 map<char, char> solucion;
  12
  13
  14 bool contradice(const string &origen, const string &destino,  map<char, char> crypt){
  15   //cout << "Contradice llamado con " << origen << " y " << destino << endl;
  16
  17   map<char, char> temp;
  18   for (int i=0; i<origen.size(); ++i){
  19     if (temp.count(origen[i]) == 1){
  20       if (temp[origen[i]] != destino[i]){
  21         return true;
  22       }
  23     }else{
  24       for (map<char, char>::iterator j = temp.begin(); j != temp.end(); ++j){
  25         if ((*j).second == destino[i]) return true;
  26       }
  27       temp[origen[i]] = destino[i];
  28     }
  29   }
  30
  31   if (origen.length() != destino.length()) return true;
  32
  33   for (int i=0; i<origen.size(); ++i){
  34     if (crypt.count(origen[i]) == 1){
  35       if (crypt[origen[i]] != destino[i]){
  36         return true;
  37       }
  38     }else{
  39       for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
  40         if ((*j).second == destino[i]) return true;
  41       }
  42     }
  43   }
  44   return false;
  45 }
  46
  47
  48
  49 void asignar(const string &origen, const string &destino, map<char, char> &crypt){
  50   if (origen.size() != destino.size()) return;
  51
  52   for (int i=0; i<origen.size(); ++i){
  53     crypt[origen[i]] = destino[i];
  54   }
  55 }
  56
  57 bool bt(int i, const vector<string> &words, map<char, char> crypt){
  58   if (i >= words.size()){
  59     solucion = crypt;
  60     return true;
  61   }
  62
  63   int len = words[i].length();
  64   set<string> possible = dict[len];
  65
  66   for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){
  67
  68     if (!contradice(words[i], (*j), crypt)){
  69       map<char, char> copia = crypt;
  70       asignar(words[i], (*j), copia);
  71
  72       if (bt(i+1, words, copia)){
  73         return true;
  74       }
  75
  76     }
  77   }
  78   return false;
  79 }
  80
  81 int main(){
  82   int n;
  83   cin >> n;
  84   while (n--){
  85     string s;
  86     cin >> s;
  87     dict[s.length()].insert(s);
  88     //cout << "agregue " << s << " al dict en la posicion " << s.length() << endl;
  89   }
  90   getchar();
  91   string line;
  92   while (getline(cin, line)){
  93     //cout << "Lei esta linea: " << line << endl;
  94
  95     if (line == ""){
  96       cout << "\n";
  97       continue;
  98     }
  99
 100     vector<string> words;
 101     stringstream ss;
 102     ss << line;
 103     string word;
 104     while (ss >> word){
 105       words.push_back(word);
 106
 107       //cout << "Empuje la palabra " << word << " a la lista " << endl;
 108
 109     }
 110     if (bt(0, words, map<char, char>() )){
 111       for (int i=0; i<line.size(); ++i){
 112         if (line[i] == ' ') cout << " ";
 113         else cout << solucion[line[i]];
 114       }
 115       cout << endl;
 116       //cout << "Hay solucion\n";
 117     }else{
 118       for (int i=0; i<line.size(); ++i){
 119         if (line[i] == ' ') cout << " ";
 120         else cout << "*";
 121       }
 122       cout << endl;
 123       //cout << "No hay solucion\n";
 124     }
 125   }
 126 }